package DataStructure.BFS;

import LeetCode.code124_maxPathSum;

import java.util.LinkedList;
import java.util.Queue;

/**
 * @Author：DijaH
 * @Date：2023/1/5 8:29 下午
 * @Version：1.0.0
 * @Description：
 * 二叉树的最小路径
 * 使用BFS框架搭建求解
 */
public class TreeNodeMinDepth {

    public static class TreeNode{
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(){}
        TreeNode(int val){this.val = val;}
        TreeNode(int val, TreeNode left, TreeNode right){
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    public static int minDepth(TreeNode root){
        if(root == null){
            return 0;
        }
        //放到一个队列中
        Queue<TreeNode> q = new LinkedList<>();
        q.offer(root);
        //root 本身就是一层。定义一个depth；
        int depth = 1;
        while (!q.isEmpty()){
            //如果不为空就一直循环
            int qz = q.size();
            for (int i = 0; i < qz; i++) {
                //将当前队列中的值向四周扩散
                TreeNode node = q.poll();
                //终止条件是叶子节点的左右节点都为空
                if(node.left == null || node.right == null){
                    return depth;
                }
                //将相邻的节点加入到队列中
                if(node.left != null){
                    q.offer(node.left);
                }
                if(node.right != null){
                    q.offer(node.right);
                }
            }
           //作为框架角度来说，如果有必要在这里depth++
            depth++;
        }
        return depth;
    }
}
